package algorithm;

public class leetcode_1277 {
    public int countSquares(int[][] matrix) {
        int m=matrix.length;
        int n=matrix[0].length;
        int [][][] dp=new int[m][n][2];
        dp[0][0][0]=matrix[0][0];
        dp[0][0][1]=matrix[0][0];
        for(int i=1;i<m;++i){
            dp[i][0][0]=matrix[i][0]+dp[i-1][0][0];
            dp[i][0][1]=matrix[i][0];
        }
        for(int j=1;j<n;++j){
            dp[0][j][0]=matrix[0][j]+dp[0][j-1][0];
            dp[0][j][1]=matrix[0][j];
        }
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                if(matrix[i][j]==1){
                    dp[i][j][0]=dp[i-1][j][0]+dp[i][j-1][0]-dp[i-1][j-1][0]+1+min(dp[i-1][j][1],dp[i][j-1][1],dp[i-1][j-1][1]);
                    dp[i][j][1]=1+min(dp[i-1][j][1],dp[i][j-1][1],dp[i-1][j-1][1]);
                }
                else{
                    dp[i][j][0]=dp[i-1][j][0]+dp[i][j-1][0]-dp[i-1][j-1][0];
                }
            }
        }
        return dp[m-1][n-1][0];
    }
    public int min(int a,int b,int c){
        if(a<b){
            return (a<c)?a:c;
        }
        else{
            return (b<c)?b:c;
        }
    }
}
